# -*- coding: utf-8 -*-
# @Time    : 2021/1/4 上午9:59
# @Author  : tgy
# https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof/

class Solution:
    def permutation(self, s: str) -> list:
        ...
        result = []
        if not s:
            return result
        chars = list(s)
        self.find(chars, 0, result)
        return result

    def find(self, chars, index, result):

        chars_len = len(chars)
        if index == chars_len:
            result.append(''.join(chars))
            return

        pres = []
        for i in range(index, chars_len):
            pass
            if chars[i] in pres:
                continue
            chars[index], chars[i] = chars[i], chars[index]
            self.find(chars, index + 1, result)
            chars[index], chars[i] = chars[i], chars[index]
            pres.append(chars[i])


if __name__ == '__main__':
    ...
    solution = Solution()
    result = solution.permutation('kzfxxx')
    print(result)
